#include <iomanip>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int InsertSort(int A[], int n){
    int temp, j;
    int M = 0, C = 0;
    for(int i = 1; i < n; i++){
        temp = A[i]; j = i - 1;
        while(j >= 0 && temp < A[j]){
            A[j+1] = A[j];
            j = j - 1;
            M++;
        }
        A[j+1] = temp;
        C++;
    }
    return M+C;
}

void PrintMas(int A[], int n) {
    for (int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    cout << endl;
}

void FillRand(int A[], int n) {
    for (int i = 0; i < n; i++) {
        A[i] = rand()%100;
    }
}

int ShellSort(int A[], int n){
    int C = 0, M = 0;
    for(int h = n/2; h > 0; h /= 2){
        for(int i = h; i < n; i++){
            int temp = A[i];
            int j = i;
            while(j >= h && A[j - h] > temp){
                C++;
                A[j] = A[j - h];
                M++;
                j -= h;
            }
            A[j] = temp;
            M++;
        }
    }
    return M+C;
}


int main(){
    int n = 100;
    int *A;
    srand(time(NULL));
    A = (int *)malloc(sizeof(int)*n);
    cout << setw(2) << "n" << setw(20) << "Кол-во К" << setw(20) << "Insert Mф+Cф" << setw(20) << "Shell Mф+Cф" << endl;
    cout << setw(27) << "сортировок" << endl;
    
    double result_log = floor((log(n) / log(2.0))-1);
    FillRand(A, n);
    int Insert_rez = InsertSort(A, n);
    FillRand(A, n);
    int Shell_rez = ShellSort(A, n);
    cout << n << setw(10) << result_log << setw(18) << Insert_rez << setw(18) << Shell_rez <<  endl;
    
    n = 200;
    result_log = floor((log(n) / log(2.0))-1);
    FillRand(A, n);
    Insert_rez = InsertSort(A, n);
    FillRand(A, n);
    Shell_rez = ShellSort(A, n);
    cout << n << setw(10) << result_log << setw(18) << Insert_rez << setw(18) << Shell_rez <<  endl;
    
    n = 300;
    result_log = floor((log(n) / log(2.0))-1);
    FillRand(A, n);
    Insert_rez = InsertSort(A, n);
    FillRand(A, n);
    Shell_rez = ShellSort(A, n);
    cout << n << setw(10) << result_log << setw(18) << Insert_rez << setw(18) << Shell_rez <<  endl;

    n = 400;
    result_log = floor((log(n) / log(2.0))-1);
    FillRand(A, n);
    Insert_rez = InsertSort(A, n);
    FillRand(A, n);
    Shell_rez = ShellSort(A, n);
    cout << n << setw(10) << result_log << setw(18) << Insert_rez << setw(18) << Shell_rez <<  endl;
    
    n = 500;
    result_log = floor((log(n) / log(2.0))-1);
    FillRand(A, n);
    Insert_rez = InsertSort(A, n);
    FillRand(A, n);
    Shell_rez = ShellSort(A, n);
    cout << n << setw(10) << result_log << setw(18) << Insert_rez << setw(18) << Shell_rez <<  endl;
    
}



